package Offer;

/**
 * 连续子数组的最大和
 * @author 是阿秋啊
 * @date 2022/04/07 20:07
 **/
public class Num42 {
    public int maxSubArray(int[] nums) {
        int[] ret = new int[nums.length];
        // ret[i]代表以元素nums[i]为结尾的连续子数组最大和
        ret[0] = nums[0];
        // max 代表ret中最大的元素
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 判断num[i] 元素位置的ret[i]的最大值
            // ret[i - 1]中永远保存的是在i元素之前的nums和最大值
            ret[i] = Math.max(nums[i] + ret[i - 1], nums[i]);
            // 判断当前ret[i]和max那个大
            max = Math.max(max,ret[i]);
        }
        return max;
    }
}
